import { measureSort, swap, testSort } from "hy-algokit";

// 先在未排序的数列中找到最小值，让后将其放在数列的起始位置
// 接着从剩余未排序的元素中找出最小值，然后放在已排序的序列末尾
// 以此类推

// 选择最小值放在最前面

export default function selectionSort(arr:number[]):number[] {
    let n = arr.length;
    // 外层循环作用，经过多少轮的找最小值
    for(let i = 0; i < n - 1; i++) {
        let minIndex = i;
        // 内层循环作用：每次找到的最小值
        for(let j = minIndex + 1; j <n; j++) {
            if(arr[j] < arr[minIndex]){
                // 将最小值的索引存储
                minIndex = j;
            }
        }
        // 当最小值的索引发生变化的时候，再去进行交换，因为可能排查一遍后，第一个索引的位置就是最小值
        if(minIndex != i){
            // i 是从哪个索引开始往后找最小值的，找到之后将循环出的最小值的索引的数据和其交换位置
            swap(arr, i ,minIndex)
        }
      
    }

    return arr;
}

testSort(selectionSort);
// 这个函数会随机给一个100万的数组，然后去测试当前排序函数排完所需要的时间，也可以自己传入第二个参数，为随机数的个数
measureSort(selectionSort);